package easy;

public class Solution_1370 {

    public String sortString(String s) {
        char[] chars = s.toCharArray();
        int[] counts = new int[26];
        for (char c : chars) {
            counts[c - 'a']++;
        }
        char[] res = new char[chars.length];
        int index = 0;
        boolean left = true;
        while (index < res.length) {
            if (left) {
                for (int i = 0; i < counts.length; i++) {
                    if (counts[i] > 0) {
                        res[index++] = (char) (i + 'a');
                        counts[i]--;
                    }
                }
            } else {
                for (int i = counts.length - 1; i >= 0; i--) {
                    if (counts[i] > 0) {
                        res[index++] = (char) (i + 'a');
                        counts[i]--;
                    }
                }
            }
            left = !left;
        }
        return new String(res);
    }

    public static void main(String[] args) {
        Solution_1370 model = new Solution_1370();
        System.out.println(model.sortString("aaaabbbbcccc"));
        System.out.println(model.sortString("rat"));
        System.out.println(model.sortString("leetcode"));
        System.out.println(model.sortString("ggggggg"));
        System.out.println(model.sortString("spo"));
    }
}
